The present invention relates to a method and device for performing high speed scale conversion from one numerical value to another, smaller numerical value.
In automation and other numerical control applications, it is usually required to convert an input value to an output value. This scaling process is required to be carried out in a very short time, without the support of a fast computation means such as a computer. For example, the one scaling scheme of interest is to convert input values in the range of 8000 to 40000 into output values in the range of 0 to 4095. It is preferred that the entire conversion process is achieved within 0.1 millisecond. At the same time, the cost to manufacture the conversion module is required to be low. The cost constraint requires that the hardware is limited to the use of a single A/D converter, and no numeral hardware support to do the scale conversion.
It is, therefore, desirable to provide a low cost method and device for high speed scale conversion wherein the errors are at sufficiently low levels.
It is an objective of the present invention to provide a method and a device to perform high speed scale conversion without using costly electronic components. This objective can be achieved by performing an approximate division of the input digital data, followed by providing a correction to the approximate result. In particular, the approximate division is carried out by right-shifting of the contents in a multi-bit shift-register, and the correction is made by a binary search process.
The method of high speed scale conversion, according to the present invention, converts an input data having a value N in the range of N1 to N2 to an output data having a value M in the range of M1 to M2, where M, N, M1, M2, N1 and N2 are positive integers, and includes the steps of:
1) determining a positive integer p such that
|qxe2x88x922p| less than |qxe2x88x922pxe2x88x921|
xe2x80x83and
|qxe2x88x922pxe2x88x921|xe2x89xa6|qxe2x88x922P+1|,
xe2x80x83where q=(N2xe2x88x92N1)/(M2xe2x88x92M1);
2) loading the value V(N)=(Nxe2x88x92N1+2pxe2x88x921) onto a multi-bit shift register and right-shifting the contents of the shift register (toward the least-significant bit) by p bits to obtain a reduced value A(N);
3) obtaining an error value E(N) from a binary search process; and
4) obtaining the value M from
M=A(N)+M1+E(N).
xe2x80x83wherein the binary search process includes the steps of:
I) obtaining an integer D such that
D=R{(N2xe2x88x92N1)*|(1/qxe2x88x921/2p)|}
xe2x80x83where R{x} is the rounded off value of x (e.g. R{2.57}=3 and R{2.49}=2);
II) establishing a list of correction values C(n) for n=0 to n=D, such that
C(n)=R{(2nxe2x88x92l)*Q}
xe2x80x83where
Q=(N2xe2x88x92N1)/2D;
xe2x80x83and
III) assigning E(N)=m, where
C(m)xe2x89xa6(Nxe2x88x92N1) less than C(m+1)
It should be noted that, for simplicity, it is possible to use the value V(N)=(Nxe2x88x92N1), instead of V(N)=(Nxe2x88x92N1+2pxe2x88x921), in Step 2.
The above-described method will be easier to appreciate with the following explanation.
When a value N within a range of N1 to N2 is required to be converted to a value M within a smaller range of M1 to M2, the usual way would be to calculate M according to the following equation:
M=R{(Nxe2x88x92N1)*(1/q)}+M1
or
Mxe2x88x92M1=R{(Nxe2x88x92N1)*(1/q)}
The usual way of converting N to M involves actual multiplication of two numbers, namely (Nxe2x88x92N1) and 1/q, which requires supporting hardware and/or a lengthy computation time. Alternatively, the value of (Mxe2x88x92M1) can be crudely approximated from (Nxe2x88x92N1)/2p and an error value is added to or subtracted from the approximate value to correct for the discrepancies. The approximate value can be obtained by loading the value of (Nxe2x88x92N1) onto a multi-bit shift-register and right-shifting the contents of the shift register by p bits. This approximation leads to an error approximately equal to:
xe2x80x83E(N)=(Nxe2x88x92N1)*|(1/qxe2x88x921/2p)|
In the digital process, E(N) is approximately equal to
E(N)=R{(Nxe2x88x92N1)*|(1/qxe2x88x921/2p)|}
It should be noted that when N=N1, there is no error and therefore E(N1)=0. When N=N2, the error is largest and approximately equal to:
E(N2)=R{(N2xe2x88x92N1)*|(1/qxe2x88x921/2p)|}=D
For the purpose of estimating the error value E(N) for any value N without actual multiplication, a binary search process can be used to obtain an approximate value of E(N). To facilitate the binary search process, the input data range (N2xe2x88x92N1) is partitioned into D approximately equal sections. Each of the D sections is denoted by an index number n, from n=0 to n=D, such that each section n is bounded by C(n) and C(n+1), where C(n) is approximately equal to (n/D)(N2xe2x88x92N1). However, in order to minimize the errors resulting from rounding off decimal numbers, it is preferred that the range is partitioned into D+1 sections and C(n) is computed according to
C(n)=R{(2nxe2x88x921)*Q}
where
Q=(N2xe2x88x92N1)/2D
The goal of a binary search is to locate the section that contains the value (Nxe2x88x92N2). In other words, the search is to locate the mth section where
C(m)xe2x89xa6(Nxe2x88x92N1) less than C(m+1)
and to assign the error value for N such that E(N)=m.
Furthermore, in order to reduce the discrepancies between this approximation method and the actual multiplication, it is desirable to load the value of (Nxe2x88x92N1+2pxe2x88x921), instead of (Nxe2x88x92N1), onto the shift-register. This is due to the fact that, after right-shifting, the value behind the decimal point will be lost regardless of its magnitude. For example, if the value Nxe2x88x92N1=15 is loaded into the shift register and right-shifted 3 bits, the result is 1 even though 15/8=1.875. It is different from the rounded off value of 1.875 which is 2. Therefore, it is preferable to load the value (Nxe2x88x92N1+4) into the shift register instead of Nxe2x88x92N1.
With all the values of C(n) being pre-calculated and electronically stored, the binary search process starts at level 1 to compare the value Z(=Nxe2x88x92N1) with C(K) where K is the middle index number between 0 and D+1 to determine which half (approximately) of the input data range (N2-N1) contains the value Z. After knowing which half of the range (N2-N1) contains the value Z, the next search will be carried out only in that half of the range. Thus, in level 2, the search range is reduced to approximately half, and the goal is to determine which quarter (approximately) of the range (N2-N1) contains the value Z. Thus, at the next level, the search range is further reduced to approximately one quarter of the range. The search continues in a similar fashion until the section in which the value Z falls is finally identified.
The major advantages of binary search are that it usually requires only a small number of search steps to obtain the error value E(N) for a given N, and that the search process can be implemented on relatively inexpensive electronic components such as microprocessors. If D is less than or equal to (2kxe2x88x921), the binary search will take at most k steps to complete.
With the method of scale conversion, according to the present invention, the total conversion time is the sum of (1) the time required for subtracting N1 (or preferably N1xe2x88x922pxe2x88x921) from N, (2) the time required for loading the value (Nxe2x88x92N1), or preferably (Nxe2x88x92N1+2pxe2x88x921), into the shift register and right-shifting the register, (3) the total number of steps in the binary search, which is equal to or less than k when D is less than or equal to (2kxe2x88x921), and (4) the time required for adding the error value and M1 to the right-shifted value.
The scale conversion method will be demonstrated herein using the following example, with N=8783, N2=40000, N1=8000, M2=4095 and M1=0.
1) q=32000/4095=7.8144078 or 1/q=0.1279687
p=3
I) (1/qxe2x88x921/2p)=0.0029687
D=R{32000*0.0029687}=R{95.00}=95
II) Q=32000/190=168.42105
C(n)=R{(2nxe2x88x921)*168.42105}, where n=0 to n=95.
C(0)=0
C(1)=R{1*168.42105}=168
C(2)=R{3*168.42105}=R{505.26316}=505
C(3)=R{5*168.42105}=R{842.10526}=842
C(14)=R{27*168.42105}=R{4547.36}=4547
C(15)=R{29*168.42105}=R{4884.21}=4884
C(16)=R{31*168.42105}=R{5221.05}=5221
C(17)=R{33*168.42105}=R{5557.89}=5558
C(91)=R{181*168.42105}=R{30484.21}=30484
C(92)=R{183*168.42105}=R{30821.05}=30821
C(93)=R{185*168.42105}=R{31157.89}=31158
C(94)=R{187*168.42105}=R{31494.74}=31495
C(95)=R{189*168.42105}=R{31831.58}=31842
2) V(N)=8783xe2x88x924000+4=787
On shift-register:       787    =          1      ⁢              xe2x80x83            ⁢      1      ⁢              xe2x80x83            ⁢      0      ⁢              xe2x80x83            ⁢      0      ⁢              xe2x80x83            ⁢      0      ⁢              xe2x80x83            ⁢      1      ⁢              xe2x80x83            ⁢      0      ⁢              xe2x80x83            ⁢      0      ⁢              xe2x80x83            ⁢      1      ⁢              xe2x80x83            ⁢      1                  right      ⁢              xe2x80x83            ⁢      shifted      ⁢              xe2x80x83            ⁢              (        3        )              =                  0        ⁢                  xe2x80x83                ⁢        0        ⁢                  xe2x80x83                ⁢        0        ⁢                  xe2x80x83                ⁢        1        ⁢                  xe2x80x83                ⁢        1        ⁢                  xe2x80x83                ⁢        0        ⁢                  xe2x80x83                ⁢        0        ⁢                  xe2x80x83                ⁢        0        ⁢                  xe2x80x83                ⁢        1        ⁢                  xe2x80x83                ⁢        1            =      98                  A      ⁡              (        N        )              =    98  
3) Since C(2)=505 and C(3)=842, we have C(2)xe2x89xa6783  less than C(3). Accordingly, E(8783)=2
4) M=98+0+2=100
The value of M obtained from Steps (1) through (4) above can be compared with the value obtained from actual multiplication:
M=R{(4095/32000)(8783xe2x88x928000)}+0=R{100.199}=100
If N=38781, V(N)=38781xe2x88x924000+4=30785
2) On shift-register:       30785    =          1      ⁢              xe2x80x83            ⁢      1      ⁢              xe2x80x83            ⁢      1      ⁢              xe2x80x83            ⁢      1      ⁢              xe2x80x83            ⁢      0      ⁢              xe2x80x83            ⁢      0      ⁢              xe2x80x83            ⁢      0      ⁢              xe2x80x83            ⁢      0      ⁢              xe2x80x83            ⁢      1      ⁢              xe2x80x83            ⁢      0      ⁢              xe2x80x83            ⁢      0      ⁢              xe2x80x83            ⁢      0      ⁢              xe2x80x83            ⁢      0      ⁢              xe2x80x83            ⁢      0      ⁢              xe2x80x83            ⁢      1                  right      ⁢              xe2x80x83            ⁢      shifted      ⁢              xe2x80x83            ⁢              (        3        )              =                  0        ⁢                  xe2x80x83                ⁢        0        ⁢                  xe2x80x83                ⁢        0        ⁢                  xe2x80x83                ⁢        1        ⁢                  xe2x80x83                ⁢        1        ⁢                  xe2x80x83                ⁢        1        ⁢                  xe2x80x83                ⁢        1        ⁢                  xe2x80x83                ⁢        0        ⁢                  xe2x80x83                ⁢        0        ⁢                  xe2x80x83                ⁢        0        ⁢                  xe2x80x83                ⁢        0        ⁢                  xe2x80x83                ⁢        1        ⁢                  xe2x80x83                ⁢        0        ⁢                  xe2x80x83                ⁢        0        ⁢                  xe2x80x83                ⁢        0            ⁢              xe2x80x83            =      3848                  A      ⁡              (        N        )              =    3848  
3) Since C(91)=30484 and C(92)=30821, we have C(91)xe2x89xa630781 less than C(92). Accordingly, E(30781)=91.
4) M=3848+0+91=3939
Actual multiplication:
M=R{(4095/32000)(38781xe2x88x928000)}+0=R{3939.006}=3939
The above two examples used to demonstrate the method of high-speed scale conversion yield a perfect match with the actual computation. It should be noted that, however, not all values N within the range of N1 and N2 will give an exactly correct value M.
The preferred version of the method of high speed scale conversion, according to the present invention, uses a microprocessor with adequate memory to store all the C(n) values and to carry out the binary search process using a search function BSX, regarding an input value N and the error value E(N). The search function BSX, for example, can be represented by:
BSX=BS(U,V,W),
and is defined as follows:
1) the search is based on the reference value C(X); and
2) if Z=C(X), go to U; if Z less than C(X), go to V; and if Z greater than C(X), go to W. Here Z=Nxe2x88x92N1.
Furthermore, another function EX is also used in the search process, which is defined as to assign E(N)=X. For example, for X=54, BSX means that the search is based on the reference value C(X)=9095 and the search function is BS54=BS(E54, BS51, BS57). If Z is equal to 9095, then E(N)=54. If Z is smaller than 9095, the search will be carried out at the next level, with BS51=BS(E51, BS50, BS52) and based on the reference value C(51). If Z is greater than 9095, then the search will be carried out at the next level, with BS57=BS(E57, BS56, BS58) and based on the reference value C(57).
In the case of D=95, the search starts at level 1 with X=48:
The following is a binary search example with N=10783, or Z=(Nxe2x88x92N1)=6783.
At Level 1, C(48)=R{95*168.42105)}=16000 and BS48=BS(E48, BS24, BS72). Because Z less than C(48), or the value (Nxe2x88x92N1) falls in the range of 0 to 16000, the search at level 2 will be carried out according to BS24.
At Level 2, C(24)=R{47*168.42105}=7916 and BS24=BS(E24, B12, B36). Because Z less than C(24), or the value (Nxe2x88x92N1) falls in the range of 0 to 7916, the search at level 3 will be carried out according to BS12.
At Level 3, C(12)=R{23*168.42105)=3874 and BS12=BS(E12, BS6, BS18). Because Z greater than C(12), or the value (Nxe2x88x92N1) falls in the range of 3874 to 7916, the search at level 4 will be carried out according to BS18.
At Level 4, C(18)=R{35*168.42105)=5895 and BS18=BS(E18, BS15, BS21). Because Z greater than C(18), or the value of (Nxe2x88x92N1) falls in the range of 5895 to 7916, the search at level 5 will be carried out according to BS21.
At Level 5, C(21)=R{41*168.42105}=6905 and BS21=BS(E21, BS20, BS22). Because Z less than C(21), or the value of (Nxe2x88x92N1) falls in the range of 5895 to 6905, the search at level 6 is carried out according to BS20.
At Level 6, C(20)=R{39*168.42105}=6568 and BS20=BS(ES20, BS19, E20). Because Z greater than C(20), or the value of (Nxe2x88x92N1) falls in the range of 6565 and 6905, the search at level 7 is not necessary because the next step is E20, or assigning E(6785)=20.
The method of scale conversion, according to the present inventin, has the advantage of being able to be carried out on a low cost device as shown in FIG. 1.